59. Spiral Matrix II

Question

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Example 1:

1 -> 2 -> 3 
          |
8 -> 9    4
|         |
7 <- 6 <- 5

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20

---

Approach

1. By observing the example, we are going to put in incremented values from the outer most of the matrix, and go inwards unti there is no more empty space.
2. The boundary for row and column is n-1 as the furthest cell is [n,n]
3. First, iterate through the top of the matrix.
4. Then, the right side of the matrix, from top to bottom with the column fixed. Note that the furthest right cell should already be filled in the previous step, hence start from the next cell under the previous last cell.
5. Then, the bottom of the matrix, from right to left with the row fixed. Similarly the right most cell was filled too, hence start from the next right-most cell.
6. Then, the left side of the matrix, from bottom to the top and stop right before the first cell that we filled in at the top row.
7. The outer layer cells should be all filled by now. We can move both the row and column iterator by 1, and shrink the boundary by 1.
8. Repeat until the iterator meets the boundary.

Solution

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int i = 0, j = 0;
        int count = 0;
        int maxRow = n - 1, maxCol = n - 1;
        vector<vector<int>> ans (n, vector<int> (n));
        
        while(i <= maxRow && j <= maxCol){
            //top, move col, fixed row
            for(int a = j; a <= maxCol; a++){
                ans[i][a] = ++count;
            }
            
            //right, move row, fixed col
            for(int b = i + 1; b <= maxRow; b++){
                ans[b][maxCol] = ++count;
            }
            
            //bottom, move col, fixed row
            for(int c = maxCol - 1; c >= j; c--){
                ans[maxRow][c] = ++count;
            }
            
            //left, move row, fixed col
            for(int d = maxRow - 1; d > i; d--){
                ans[d][j] = ++count;
            }
            
            i++;
            j++;
            maxRow --;
            maxCol --;
        }
        return ans;
    }
};